The present invention relates generally to digital communications systems, such as broadband wireless access (BWA) communications systems, which are based on the principle of time division multiple access (TDMA) and, more particularly, to a method and apparatus for scheduling upstream traffic in such systems.
Over the past few decades, various system architectures have been developed in order to satisfy the public""s insatiable thirst for high-rate data communications. These architectures typically employ high-capacity media such as radio, coaxial cable or optical fiber to deliver bi-directional communications services to end customers (subscribers).
In a wireless system, i.e., when radio links are used, it is common to speak of a xe2x80x9ccellularxe2x80x9d architecture, in which a base transceiver station (BTS) is positioned at the center of a service area (normally called a xe2x80x9ccellxe2x80x9d) and communicates over the air with multiple customer premises equipment (CPE) units located within the cell. Typically, the direction of communication from the BTS to the CPE units is called the xe2x80x9cdownstreamxe2x80x9d direction and the reverse direction of communication is referred to as the xe2x80x9cupstreamxe2x80x9d direction.
In order to send separate downstream data streams to multiple CPE units at the same time, the data is usually multiplexed in frequency or in time. Multiplexing in frequency can be achieved by assigning a distinct downstream carrier frequency and a distinct upstream carrier frequency to each CPE unit. More commonly, however, downstream data destined for several CPE units is multiplexed in time and is transmitted at a common xe2x80x9cforwardxe2x80x9d carrier frequency and upstream data originating from several CPE units is multiplexed in time and is transmitted at a common xe2x80x9creversexe2x80x9d carrier frequency. A cellular system that uses time-division multiplexing techniques is usually referred to as a time-division multiple-access (TDMA) cellular system.
In the particular case of a broadband wireless access (BWA) system, multiplexing in time is achieved differently for the two directions of communication. In the downstream direction, for example, the BTS commonly transmits a series of MPEG (Motion Picture Experts Group) packets of length 188 bytes each. The MPEG packets are destined for different CPE units but are received by all CPE units within range, since the radio link is a shared resource. In order to ensure that the MPEG packet destined for a particular CPE unit is processed by that unit but discarded by others, the BTS may encode each packet header with the identity of the intended recipient. Clearly, in this topology, the BTS has control over all transmissions occurring in the downstream direction and is capable of managing the downstream bandwidth allocated to each CPE unit.
In the upstream direction, the time structure of the communications link is divided into scheduling periods having a fixed number of time slots (also called mini-slots) per scheduling period. Since individual CPE units cannot listen to one another""s transmissions, they cannot self-regulate their access to the upstream link. Thus, it is necessary for the BTS to centrally manage the allocation of mini-slots to be used by each CPE unit for sending data in the upstream direction. The number of xe2x80x9cupstreamxe2x80x9d mini-slots assigned to each CPE unit as computed by the BTS is sent to each concerned CPE unit, e.g., encoded into the body of an MPEG packet destined for each CPE unit.
The number of mini-slots allocated by the BTS to a given CPE unit for transmission in the upstream direction should satisfy, as precisely as possible, the upstream bandwidth demands of the given CPE unit. Otherwise, the result will be either lost data or bandwidth wastage. For example, if the number of allocated mini-slots is not sufficient to accommodate the upstream bandwidth demands of a given CPE unit, then upstream data may be lost or delayed until a following scheduling period. On the other hand, if an excessive number of mini-slots is assigned to a given CPE unit, the result may be that other CPE units with legitimate bandwidth demands are being deprived of upstream bandwidth which actually remains unused by the given CPE unit.
Thus, it is important for the BTS to have a precise idea of the upstream bandwidth demands of each CPE unit in order to efficiently manage the often scarce bandwidth resources available on the upstream link. Such management is often achieved using a bandwidth allocation algorithm at the BTS.
Most conventional bandwidth allocation algorithms are request-based, meaning that each CPE unit transmits to the BTS a message indicative of the amount of upstream bandwidth that it currently requires. A problem with request-based bandwidth allocation algorithms is that there is usually a delay of at least a few milliseconds associated with generating, transmitting, processing and responding to such a message. Unfortunately, a few milliseconds"" delay in deciding whether to increase or decrease the allocated upstream bandwidth can be fatal to the operation of a high-rate communications system, as a large amount of data can be is lost in such a seemingly short amount of time.
Thus, there is a need to provide a mechanism for managing upstream link access, whereby the bandwidth demands of multiple CPE units in a broadband wireless access system can be accurately estimated and whereby the upstream bandwidth can be appropriately allocated by the BTS.
It is an object of the present invention to mitigate or obviate one or more disadvantages of the prior art.
Accordingly, the BTS of the present invention runs a scheduler which estimates the number of cell arrivals occurring in the current scheduling period based on previous cell arrival time information from each CPE unit. The estimated number of cell arrivals is used by the scheduler to allocate future bandwidth for use by each CPE unit. Rather than respond in a delayed manner to a bandwidth deficiency or surplus at an individual CPE unit, the invention allows the BTS to produce an estimate of a CPE unit""s bandwidth demands, resulting in more efficient bandwidth utilization and reduced cell loss ratio.
The invention may be summarized broadly as a method of allocating bandwidth in a communications system, including the steps of receiving a plurality of actual arrival times associated with respective data units; determining, as a function of the received actual arrival times, a number of data units expected to have actual arrival times in a time interval beginning after the most recently received actual arrival time; and allocating sufficient bandwidth to transmit the expected number of data units.
Preferably, the expected number of data units is determined by determining a calibrated arrival time of a subsequent data unit; advancing the calibrated arrival time by constant increments until it is within said time interval; and setting the expected number of data units equal to one plus the number of times that the advanced calibrated arrival time can be further advanced while remaining within said time interval.
Alternatively, the calibrated arrival time could be advanced by constant increments until it is within less than expected number of data units would equal the number of times that the advanced calibrated arrival time can be advanced by said increments while remaining within said time interval.
Preferably, the calibrated arrival time of the subsequent data unit is determined by first comparing the actual arrival time of a previous data unit with a calibrated arrival time of the previous data unit. If the actual arrival time of the previous data unit is within a predetermined range of the calibrated arrival time of the previous data unit, the calibrated arrival time of the subsequent data unit is created by computing a function of the actual arrival time and the calibrated arrival time of the previous data unit and advancing the result by the increment. Otherwise, the calibrated arrival time of the subsequent data unit is created by advancing the actual arrival time of the previous data unit by the increment.
The invention may also be broadly summarized as an article of manufacture, including a computer usable medium having computer readable program code means embodied therein for causing bandwidth to be allocated in a communications system. The computer readable program code means includes computer readable program code means for causing a computer to execute the above-described steps of the invention. Such a computer could be located in a base transceiver station.
Also, the invention may be summarized broadly as a method of allocating bandwidth for transmitting data units from a first communications device (e.g., CPE) to a second communications device (e.g., BTS). The method includes the steps of the CPE determining arrival time information associated with each data unit and sending arrival time information associated with at least one data unit to the BTS; the BTS allocating future bandwidth to the CPE as a function of the arrival time information received from the CPE; the BTS then sending information to the CPE in which the allocated future bandwidth is specified; and the CPE grouping a number of the data units into a burst packet occupying the allocated bandwidth and sending the burst packet to the BTS.
Preferably, bandwidth is allocated as a number of time slots to be used by the CPE in a future scheduling period. Preferably, the step of the BTS allocating future bandwidth includes the BTS estimating the number of data units arriving at the CPE in the current scheduling period and determining the number of time slots required to transmit a burst packet encapsulating the estimated number of data units.
The invention can also be broadly summarized as a scheduler, including a calibration unit and an unsolicited bandwidth allocation unit connected to the scheduler. The calibration unit is operable to receive arrival time information associated with a plurality of data units and to determine, as a function of the arrival time information, a calibrated arrival time for a next data unit. The unsolicited bandwidth allocation unit is operable to determine the number of data units expected to arrive in a time interval and to allocate sufficient bandwidth to accommodate the expected number of data units.
Also, the invention may be summarized broadly as a communications device including a data unit extraction module for extracting the actual arrival time associated with each of a plurality of data units; and a scheduler connected to the data unit extraction module, for receiving the actual arrival times from the data unit extraction module, for determining, as a function of the actual arrival times, a number of data units expected to arrive in a time interval beginning after the most recently received actual arrival time, and for allocating sufficient bandwidth to transmit the expected number of data units.
The invention could also be broadly summarized as a communications device, including a frame create module connected to a burst create module. The frame create module is operable to receive data units from a data unit generation module, to determine arrival time information associated with each data unit, to organize the data units into frames and to encode the frame with the arrival time information of each data unit so organized.
For its part, the burst create module is operable to receive, during each of a plurality of successive scheduling periods, instructions to transmit frames during a specified set of time slots in a specified scheduling period; to create a burst packet from the frames (where the burst packet occupies the number of time slots in the specified set of time slots); to arrange the burst packet to fit into the specified set of time slots; and to transmit the burst packet in the specified set of time slots in the specified scheduling period.